\section{Introduction}

Secure Multi Party Computation (SMC) is a way for $n$ parties to
evaluate a function $f(x_1,\ldots,x_n) = (y_1,\ldots, y_n) = y$ where
each party $P_i$ gives input $x_i$ and receives output $y_i$. We
assume the existence of some adversary who is able to corrupt a number
of the participating parties. We denote the set of corrupt players as
$\w{C}$. A passive adversary can see what is send to and from the
corrupted parties whereas an active adversary can influence what is
send to other parties from the corrupted ones. We require of a SMC
protocol that the following two conditions are satisfied:
\begin{itemize}
\item Correctness: All parties receive correct outputs based on the
  inputs.
  \item Privacy: The adversary cannot learn any more information than
    $\{x_i,y_i\}_{i\in \w{C}}$, i.e. the input and output of the
    corrupted parties.
\end{itemize}

In this thesis, we assume that the adversary cannot corrupt or control
more than $t<\nicefrac{n}{3}$ parties. Also, we assume that the
adversary is actively corrupting parties. This means that it is
allowed for up to $t$ of the parties to work together, send false
information and thus try to make the computation fail. This slightly
weak notion of security will be specified later.

The applications to the SMC field of cryptology is wide, and
oftentimes it is more useful to implement a specific solution to a
problem, than use the general method simply because the general method
becomes impractical. The first example of an application in the
history of SMC is the millionaire problem where two millionaires would
want to know who is the richer without letting the other know his
net-worth. Another, maybe more useful, application of SMC could be
voting. If you do not trust a single entity to count the number of
votes, you could instead use SMC to keep your vote secret, while still
getting to know the outcome of the vote. If this could be implemented
in countries with a high probability of corruption in the government,
maybe instigated by the UN, we could get a fair and democratic vote,
since the government could not threaten the population as they would
have perfect privacy - even if the corrupt government tried to stall
the vote for years they would not be able to break the
security\footnote{Given usage of the solution presented by \cite{mpc1}
  and implemented in this thesis} (given they only had control over a
maximum of $\nicefrac{1}{3}$ of the population).

Even though general solutions to any SMC application are not optimal,
recent developments have enabled us to do multiparty computation with
linear communication in the number of multiplication gates in the
circuit such as \cite{mpc1} and \cite{mpc2}. The reason we use this
form of arithmetic circuits, is the fact that every function can be
computed using addition and multiplication gates. Thus, if we can
evaluate such gates, we have the ability to compute every possible
function. Though certainly not a specific solution to any SMC problem,
the solution I am considering in this thesis is still of highly
theoretical value, since none before had a perfectly secure multiparty
computation protocol which only uses linear communication
cost. Showing that this is indeed possible in practice is therefore
the main goal of this thesis and the implementation work behind it.

This thesis will first go through some preliminaries such as how we
model the world and explain about a few tools that we need for the
project. Having the basic building blocks ready, we can now delve
deeper into the actual protocol and the sub-protocols used. This is
followed by an explanation of the actual implementation as well as the
frameworks used. Then the results of running the protocol are
evaluated with different variables and the whole project is concluded
upon. I will finish off with a discussion about possible future work I
might have done had the time allowed for it.
